//bsm
//#define LENGTH                    (56)
//unsigned int gene_code[LENGTH] = {0,1,1,0,1,1,1,0,0,1,0,0,1,0,1,1,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0,0,1,1,0,1,0,1,0,0,};

//bst
//#define LENGTH                    (32)
//unsigned int gene_code[LENGTH] = {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0};

//bcs
#define LENGTH                    (72)
unsigned int gene_code[LENGTH] = {0,0,0,1,0,1,0,0,0,0,0,0,1,1,1,0,1,1,1,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,1,0,0,0,0};	

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>
	double *roulette;
//change bits
unsigned int *get_bits(unsigned int num[LENGTH], int bitm, int bitn){
	unsigned int temp1[LENGTH]={0};
	unsigned int temp2[LENGTH]={0};
	unsigned int temp3[LENGTH]={0};

	for(int i=0;i<bitm;i++){
		temp1[i]=num[i];
	}
	for(int i=bitm,k=0;i<bitn;i++,k++) {
		temp2[k]=num[i];
	}
	for(int i=bitn,k=0;i<LENGTH;i++,k++) {
		temp3[k]=num[i];
	}
	int k=0;
	int n=0;
	for(int j=0;j<LENGTH;j++){
		if(j<(LENGTH-bitn)) num[j]=temp3[j];
		else if(j<(LENGTH-bitm)) num[j]=temp2[k++];
		else num[j]=temp1[n++];
	}
	return num;
}

unsigned int change(char bin[LENGTH]){
	int n = 0,i;
    for(i = 0; i<LENGTH; i++)
    {
    	//printf("%c\n",bin[i]);
        n*=2;
        n+=bin[i]-'0';
        //printf("%d\n",n);
    }
    printf("n=%x\n",n);
	return n;
}

//calculate fitness 
unsigned int fitness(unsigned int str1[LENGTH], unsigned int str2[LENGTH]) {
	int dif = 0;
	for(int i = 0; i<LENGTH; i++) {
		if(str1[i] != str2[i])	dif++;
	}
	return dif;
}


int main(){
	//input case
	//bst
	//unsigned int gene_code[LENGTH] = {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0};
	//bcs
	//unsigned int gene_code[LENGTH] = {0,0,0,1,0,1,0,0,0,0,0,0,1,1,1,0,1,1,1,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,1,0,0,0,0};	
	//bsm
	//unsigned int gene_code[LENGTH] = {0,1,1,0,1,1,1,0,0,1,0,0,1,0,1,1,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0,0,1,1,0,1,0,1,0,0,};
	
	int cnt=1000;
	while(cnt){
		srand((unsigned)time(NULL)); 
		//cross
		unsigned int pos1 = rand() % LENGTH + 1;
		unsigned int pos2 = rand() % LENGTH + 1;
		unsigned int minpos=0;
		unsigned int maxpos=0;
		double dif=0;

		if(pos1<pos2) {
			minpos = pos1;
			maxpos = pos2;
		}
		else{
			minpos = pos2;
			maxpos = pos1;
		}
		//printf("minpos=%d\n",minpos);
		//printf("maxpos=%d\n",maxpos);	
		unsigned int *a = get_bits(gene_code,minpos,maxpos);
	
	//mutation
		unsigned int mutate_bit = rand() % LENGTH;
		//printf("mutate_bit=%d\n",mutate_bit);
		//printf("%d\n",a[mutate_bit]);
		a[mutate_bit] = (a[mutate_bit] + 1) % 2;
		//printf("%d\n",a[mutate_bit]);
	
		//print a[]
		for(int i=0;i<LENGTH;i++)	printf("%x",a[i]);
		printf("\n");
	//calculate fitness 
		dif=fitness(gene_code, a); 
		if(dif>(LENGTH/2)) break;
		
	//2->16
		/*
		char hex[LENGTH];
		for(int i=0;i<LENGTH;i++)	sprintf(hex,"%d",a[i]);
		printf("%d\n",a);	
		*hex=change((char*)a);
	
		printf("%x",hex);
		*/
		
	//print to file
		FILE *fp;
		char hex[LENGTH];
		fp=fopen("bcs.txt","a");
		for(int i=0;i<LENGTH;i++)	fprintf(fp,"%x",a[i]);
		fprintf(fp,"\n");
		//fgets(hex,LENGTH,fp);
		//unsigned int hex1=change(hex);
		//fprintf(fp,"%x",hex1);
		cnt--;
	}
	
} 



